#ifndef __POLYGON_TRIANGULATION__
#define __POLYGON_TRIANGULATION__

#include <list>
#include <vector>
#include <map>
#include <functional>
#include <unordered_set>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_hierarchy_2.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Aff_transformation_2.h>

#include "../common/polytope.h"

namespace Packing_common {


// ------------- My stuff to extend CGAL --------------------------

    struct VertexDecoration {
		VertexDecoration(int group_id_ = -2) : group_id(group_id_) { }
        int group_id ;
    } ;

    struct CellDecoration {

        CellDecoration() : visited(false) {    }
	
        bool visited ;
        //vec2 dual ;
        //bool dual_outside ;
    } ;


// ------------- CGAL stuff ---------------------------------

    // ----------------------- A CGAL::Vertex with decoration ------------------
    template < class Gt, class Vb = CGAL::Triangulation_vertex_base_2<Gt> >
    class Vertex : public  Vb, public VertexDecoration  {
        typedef Vb superclass;
    public:
        typedef typename Vb::Vertex_handle      Vertex_handle;
        typedef typename Vb::Face_handle        Face_handle;
        typedef typename Vb::Point              Point;
        
        template < typename TDS2 >
        struct Rebind_TDS {
            typedef typename Vb::template Rebind_TDS<TDS2>::Other Vb2;
            typedef Vertex<Gt,Vb2> Other;
        } ;
        
    public:
        Vertex() : superclass() {}
        Vertex(const Point & p) : superclass(p) {}
        Vertex(const Point & p, Face_handle f) : superclass(f,p) {}
        Vertex(Face_handle f) : superclass(f) {}
    } ;


    // ----------------------- A CGAL::Cell with decoration for nonconstrained triangulation ------------------
    template < class Gt, class Cb = CGAL::Triangulation_face_base_2<Gt> >
    class Cell : public Cb, public CellDecoration {
        typedef Cb superclass;
    public:
        typedef typename Cb::Vertex_handle      Vertex_handle;
        typedef typename Cb::Face_handle        Face_handle;
        template < typename TDS2 >
        struct Rebind_TDS {
            typedef typename Cb::template Rebind_TDS<TDS2>::Other Cb2;
            typedef Cell<Gt,Cb2> Other;
        };


        Cell() : superclass() {  }
        Cell(
            Vertex_handle v0, Vertex_handle v1, Vertex_handle v2
        ) : superclass(v0,v1,v2) { }
            
        Cell(
            Vertex_handle v0, Vertex_handle v1, Vertex_handle v2, 
            Face_handle n0, Face_handle n1, Face_handle n2 
        ) : superclass(v0,v1,v2,n0,n1,n2) { }

    } ;
    
	//typedef CGAL::Exact_predicates_inexact_constructions_kernel K ;
	//typedef Vertex<K> Vb ;
	//typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vb> Vbh;
	//typedef Cell<K>   Cb ;
	//typedef CGAL::Triangulation_data_structure_2<Vbh,Cb> TDS;
	//typedef CGAL::Delaunay_triangulation_2<K, TDS> Delaunay_triangulation_2 ;

    class Polygon_triangulation 
	{
		typedef CGAL::Exact_predicates_inexact_constructions_kernel K ;
		typedef Vertex<K>										Vb ;
		typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vb> Vbh;
		typedef Cell< K, CGAL::Constrained_triangulation_face_base_2<K> >		Cb ;
		typedef CGAL::Triangulation_data_structure_2<Vbh,Cb>	TDS;
		
		typedef CGAL::Delaunay_triangulation_2<K, TDS>			Delaunay_triangulation_2 ;
		typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS, CGAL::Exact_predicates_tag> Constrained_Delaunay_triangulation_2;
	
	public:
		// in this implementation, constrained delaunay triangulation is used as the triangulation
		// its alias as Triangulation_2 because the outside code using this class don't need changing if we change to another kind of triangulation 
		typedef Constrained_Delaunay_triangulation_2			Triangulation_2; 
		typedef CGAL::Aff_transformation_2<K>					Transformation_2;

	private:
		typedef Triangulation_2::Point	Point_2;
		typedef Triangulation_2::Vertex_handle	Vertex_handle;
		typedef Triangulation_2::Face_handle	Face_handle;

	public:
		Polygon_triangulation() : open(false), nb_groups(0) { }
		void begin_insert()
		{
			open = true;
			cdt.clear();
			nb_groups = 0;
		}
		void insert(const Packing_polygon& polygon, int group_no, int sample_nb = 20);
		void end_insert();
		void update_triangulation(); 

		template <class Operation>
		void update_vertex_group(int group_id, Operation t);
		
		void swap_vertex_group(int group_id, int another_group_id)	
		{ std::swap(vert_groups[group_id], vert_groups[another_group_id]);  }

		const std::list<Vertex_handle>& vertex_group(size_t group_id)
		{
			return vert_groups[group_id];
		}

		const Triangulation_2& triangulation() { return cdt; }

		const std::vector< CGAL_polygon >& polygon_cat_cells() const { return polygonal_cat_cells; }
		// draw and debug
		void draw_triangulation() const;
		void draw_CAT() const;
		void draw_polygonal_CAT() const;
		void stub() const { std::cout<<"The # of faces in triangulation: "<<cdt.number_of_faces()<<std::endl; }

	private:
		void compute_CAT(); // compute the CAT cells
		void polygonize_CAT(); // convert the CAT consisting of segments into cgal polygon
		void group_vertices();
		void retrieve_vacant_neighbor(size_t group_id, std::list< std::pair<Point_2, Point_2> >& vnbnd);

	private:
		Constrained_Delaunay_triangulation_2 cdt; // the Delaunay triangulation is used to initialize the triangulation
		bool open;
		int nb_groups;
		std::vector< std::list<Point_2> > cat_cells;
		std::vector< CGAL_polygon > polygonal_cat_cells;
		std::vector< std::list<Vertex_handle> > vert_groups;
		std::list<Vertex_handle> bnd_verts;
		std::vector< std::list<Point_2> > vacant_neighbor;
    } ;

	template <class Operation>
	void Polygon_triangulation::update_vertex_group(int group_id, Operation t)
	{
		if (group_id >= nb_groups)	return;
		std::list<Vertex_handle> *vg;
		if (group_id < 0)
			vg = &bnd_verts;
		else
			vg = &vert_groups[group_id];
		std::for_each(vg->begin(), vg->end(), t);
	}

}


#endif
